#include <iostream>
#include <vector>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// class Solution {
//     vector<TreeNode*> vec;
// public:
//     TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
//         if(root == NULL || p == NULL) return NULL;
//         dfs(root);
//         int i;
//         for(i = 0;i < vec.size();++i)
//         {
//             if(vec[i] == p) break;
//         }
//         cout << i << " " << vec.size() << endl;
//         if(i >= vec.size() - 1) return NULL;
//         return vec[++i];
//     }
//     void dfs(TreeNode* root)
//     {
//         if(root == NULL) return;
//         if(root->left != NULL)
//         {
//             dfs(root->left);
//         }
//         vec.push_back(root);
//         if(root->right != NULL)
//         {
//             dfs(root->right);
//         }
//     }
// };

class Solution {
    vector<TreeNode*> vec;
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(!root) return NULL;
        if(root->val <= p->val)
        {
            return inorderSuccessor(root->right,p);
        }
        else
        {
            TreeNode* leftRet = inorderSuccessor(root->left,p);
            if(!leftRet) return root;
            else return leftRet;
        }
    }

};


int main()
{
    TreeNode h1(1);
    TreeNode h2(2);
    TreeNode h3(3);
    TreeNode h4(4);
    TreeNode h5(5);
    TreeNode h6(6);
    h5.left = &h3;
    h5.right = &h6;
    h3.left = &h2;
    h3.right = &h4;
    h2.left = &h1;
    Solution sol;
    cout << sol.inorderSuccessor(&h5,&h6)->val << endl;
    return 0;
}
